package com.zlsy.learning.leetcode.queue;

/**
 * @author zhouliang
 * @date 2020/8/13 10:06 用数组实现一个队列
 */
public class ArrayQueue {
  /** 队列存储元素 */
  private String[] items;
  /** 队列长度 */
  private int n = 0;
  /** 队列的头指针 */
  private int head = 0;
  /** 队列的尾指针 */
  private int tail = 0;

  /** 申请一个大小为capacity的数组 */
  public ArrayQueue(int capacity) {
    if (capacity < 0) {
      throw new IllegalArgumentException("capacity error！");
    }
    items = new String[capacity];
    n = capacity;
  }

  /**
   * 入队
   *
   * @param item 入队元素
   * @return 是否入队成功
   */
  public boolean enqueue(String item) {
    if (tail == n) {
      return false;
    }
    items[tail] = item;
    ++tail;
    return true;
  }

  /**
   * 升级入队的方法：当head前面有空位的时候我们移动head到队列头
   *
   * @param item
   * @return
   */
  public boolean upgradeEnqueue(String item) {
    if (tail == n) {
      // 队列满了
      if (head == 0) {
        return false;
      }
      // i必然大于0
      //      int i = tail - head;
      for (int i = head; i < tail; i++) {
        items[i - head] = items[i];
        items[i] = "";
      }
      tail = tail - head;
      head = 0;
    }
    items[tail] = item;
    ++tail;
    return true;
  }

  /**
   * 出队
   *
   * @return 出队元素
   */
  public String dequeue() {
    if (head == tail) {
      return null;
    }
    String item = items[head];
    items[head] = "";
    ++head;
    return item;
  }
}
